import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Trie {
    private Trie[] tries;
    private boolean bool;
    public Trie() {
        tries=new Trie[26];
        bool=false;
    }

    public void insert(String word) {
        Trie node=this;
        for(int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            int index=ch-'a';
            if(node.tries[index]==null){
                node.tries[index]=new Trie();
            }
            node=node.tries[index];
        }
        node.bool=true;
    }

    public boolean search(String word) {
        Trie node=searchPrefix(word);
        return node!=null&&node.bool;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix)!=null;
    }
    public Trie searchPrefix(String s){
        Trie node=this;
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            int index=ch-'a';
            if(node.tries[index]==null){
                return null;
            }
            node=node.tries[index];
        }
        return node;
    }
}










class Trie1 {
    private Trie1[] tries;
    private boolean bool;
    public Trie1() {
        tries=new Trie1[26];
        bool=false;
    }

    public void insert1(String word) {
        Trie1 node=this;
        for(int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            int index=ch-'a';
            if(node.tries[index]==null){
                node.tries[index]=new Trie1();
            }
            node=node.tries[index];
        }
        node.bool=true;
    }

    public boolean search1(String word) {
        Trie1 node=searchPrefix1(word);
        return node!=null&&node.bool;
    }

    public boolean startsWith1(String prefix) {
        return searchPrefix1(prefix)!=null;
    }
    public Trie1 searchPrefix1(String s){
        Trie1 node=this;
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            int index=ch-'a';
            if(node.tries[index]==null){
                return null;
            }
            node=node.tries[index];
        }
        return node;
    }
}




















public class project {
    public int[][] merge(int[][] intervals) {
        List<int[]> list=new ArrayList<>();
        int len=intervals.length;
        if(len==0){
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        for(int i=0;i<len;i++){
            int x=intervals[i][0];
            int y=intervals[i][1];
            if(list.size()==0||list.get(list.size()-1)[1]<x){
                list.add(new int[]{x,y});
            }else{
                list.get(list.size()-1)[1]=Math.max(y,list.get(list.size()-1)[1]);
            }
        }
        return list.toArray(new int[list.size()][]);
    }



















    public int[] maxSlidingWindow(int[] nums, int k) {
        int len=nums.length;
        if(len<2){
            return nums;
        }
        int[] arr1=new int[len];
        int[] arr2=new int[len];
        for(int i=0;i<len;i++){
            if(i%k==0){
                arr1[i]=nums[i];
            }else{
                arr1[i]=Math.max(arr1[i-1],nums[i]);
            }
        }
        for(int i=len-1;i>=0;i--){
            if(i==len-1||(i+1)%k==0){
                arr2[i]=nums[i];
            }else{
                arr2[i]=Math.max(arr2[i+1],nums[i]);
            }
        }
        int[] arr=new int[len-k+1];
        for(int i=0;i<len-k+1;i++){
            arr[i]=Math.max(arr1[i+k-1],arr2[i]);
        }
        return arr;
    }














    private TreeNode prev=null;
    private int[] arr;
    private int max;
    private int ret;
    private int cur;
    public int[] findMode(TreeNode root) {
        dfs(root);
        arr=new int[ret];
        prev=null;
        ret=0;
        cur=0;
        dfs(root);
        return arr;
    }
    public void dfs(TreeNode root){
        if(root==null){
            return;
        }
        dfs(root.left);
        if(prev!=null&&prev.val==root.val){
            cur++;
        }else{
            cur=1;
        }
        if(cur>max){
            max=cur;
            ret=1;
        }else if(cur==max){
            if(arr!=null){
                arr[ret]=root.val;
            }
            ret++;
        }
        prev=root;
        dfs(root.right);
    }












    public String firstPalindrome(String[] words) {
        boolean bool;
        for(String s : words){
            int len=s.length();
            int left=0;
            int right=len-1;
            bool=true;
            while (left<right){
                if(s.charAt(left)==s.charAt(right)){
                    left++;
                    right--;
                }else{
                    bool=false;
                    break;
                }
            }
            if(bool){
                return s;
            }
        }
        return "";
    }





















    public int minimumSwitchingTimes(int[][] source, int[][] target) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<source.length;i++){
            for(int j=0;j<source[i].length;j++){
                map.put(source[i][j],map.getOrDefault(map.get(source[i][j]),0)+1);
            }
        }
        int ret=0;
        for(int i=0;i<target.length;i++){
            for(int j=0;j<target[i].length;j++){
                if(map.get(target[i][j])==null){
                    ret++;
                }else{
                    map.put(target[i][j],map.get(target[i][j])-1);
                    if(map.get(target[i][j])<0){
                        ret++;
                    }
                }
            }
        }
        return ret;
    }










    public String tictactoe(int[][] moves) {
        int len=moves.length;
        int[] target=moves[len-1];
        int row=0;
        int col=0;
        int just=0;
        int loss=0;
        int index=len-1;
        while (index>=0){
            int[] tmp=moves[index];
            if(tmp[0]==target[0]){
                row++;
            }
            if(tmp[1]==target[1]){
                col++;
            }
            if(tmp[0]==tmp[1]){
                just++;
            }
            if(tmp[0]+tmp[1]==2){
                loss++;
            }
            index-=2;
            if(row>=3||col>=3||just>=3||loss>=3){
                return (len%2==0)?"B":"A";
            }
        }
        if(len<9){
            return "Pending";
        }
        return "Draw";
    }












    public int numRookCaptures(char[][] board) {
        int row=board.length;
        int col=board[0].length;
        int[] dx={1,-1,0,0};
        int[] dy={0,0,1,-1};
        int ret=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j]=='R'){
                    for(int k=0;k<4;k++){
                        int x=i;
                        int y=j;
                        while (true){
                            x+=dx[k];
                            y+=dy[k];
                            if(x<0||x>=row||y<0||y>=col||board[x][y]=='B'){
                                break;
                            }
                            if(board[x][y]=='p'){
                                ret++;
                                break;
                            }
                        }
                    }
                    return ret;
                }
            }
        }
        return ret;
    }















    public int repeatedStringMatch(String a, String b) {
        StringBuffer sb=new StringBuffer();
        int lenA=a.length();
        int lenB=b.length();
        int ret=0;
        while (sb.length()<b.length()){
            ret++;
            sb.append(a);
        }
        sb.append(a);
        int index=sb.indexOf(b);
        if(index==-1){
            return -1;
        }
        return index+b.length()>a.length()*ret?ret+1:ret;
    }
}
